package SubjectQueue;

import java.util.HashSet;
import java.util.Stack;

public class RemoveDuplicates {

/**
 * 难度：简单
 * 
 * 1047. 删除字符串中的所有相邻重复项
 * 	给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
 * 	在 S 上反复执行重复项删除操作，直到无法继续删除。
 * 	在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
 * 
 * 示例：
 * 	输入："abbaca"
 * 	输出："ca"
 * 	解释：
 * 	例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可
 * 	以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重
 * 	复项删除操作，所以最后的字符串为 "ca"。
 * 
 * 提示：
 * 	1 <= S.length <= 20000
 * 	S 仅由小写英文字母组成。
 * 
 * */
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		RemoveDuplicates rd = new RemoveDuplicates();
		System.out.println(rd.removeDuplicates("abbaca"));
	}
	//自己写
	public String removeDuplicates(String S) {
		Stack<Character> stack = new Stack<>();
		for(int i=0;i<S.length();i++) {
			//把没出现过的收入栈
			if(stack.isEmpty() || S.charAt(i)!=stack.peek()) {
				stack.push(S.charAt(i));
			}else {
				//把重复出现的弹出
				stack.pop();
			}
		}
		StringBuilder sb = new StringBuilder();
		//最后从栈中没重复的字母组合回字符串
		while(!stack.isEmpty()) {
			sb.append(stack.pop());
		}
		sb.reverse();
		return sb.toString();
    }
	//方法一：替换函数
	public String removeDuplicates1(String S) {
	      // generate 26 possible duplicates
	        HashSet<String> duplicates = new HashSet<>();
	        StringBuilder sb = new StringBuilder();
	        //从a到z重复的字母组合一遍，存到duplicates
	        for (char i = 'a'; i <= 'z'; ++i) {
	            sb.setLength(0);
	            sb.append(i); 
	            sb.append(i);
	            duplicates.add(sb.toString());
	        }
	        int prevLength = -1;
	        while (prevLength != S.length()) {
	            prevLength = S.length();
	            //如果有重复字母就替换成""
	            for (String d : duplicates) S = S.replace(d, "");
	        }

	      return S;
	}
	//方法二：栈
	public String removeDuplicates2(String S) {
        StringBuilder sb = new StringBuilder();
        int sbLength = 0;
        for (char character : S.toCharArray()) {
            if (sbLength != 0 && character == sb.charAt(sbLength - 1))
                sb.deleteCharAt(sbLength-- - 1);
            else {
                sb.append(character);
                sbLength++;
            }
        }
        return sb.toString();
	}
}

